#include <iostream>

#include "set_permute.h"
class CAM
{
public:

  CAM(int vertex_count);
  ~CAM();
  int loc(int location);
  int loc(int row, int column);
  int get_loc(int row, int column);
  void put_loc(int row, int column, int value);
  void reorder(int *given, int *result);
  void reorder(std::vector<int> *given, int *result);

  void add_vertex(int id, int label);
  void add_edge(int id1, int id2, int label);

  void get_vertex_indices(int *indices);
  void get_vertex_labels(int *labels);
  void swap(int *i, int *j);

  bool check_maximal();
  bool check_lower(int *given);
  
  void print();
  void print(int *given);
private:
  int vertex_count_;
  int *matrix;
};

CAM::CAM(int vertex_count): vertex_count_(vertex_count)
{
  matrix = new int[(vertex_count_ * (vertex_count_ + 1))/2];
  for(int i = 1; i <= vertex_count_; i++)
    for(int j = 1; j <= i; j++)
      put_loc(i,j,0);
}

CAM::~CAM()
{
  delete[] matrix;
}

int CAM::loc(int location)
{
  return location - 1;
}

int CAM::loc(int row, int column)
{
  int  adjusted_row = row - 1;
  int adjusted_column = column - 1;

  if (adjusted_row == 0 && adjusted_column == 0)
    return 0;
  else 
    return ((adjusted_row * (adjusted_row + 1))/2) + adjusted_column;
}

int CAM::get_loc(int row, int column)
{
  return matrix[loc(row, column)];
}

void CAM::put_loc(int row, int column, int value)
{
  matrix[loc(row, column)] = value;
}

void CAM::reorder(int *given, int *result)
{
  for(int i = 1; i <= vertex_count_; i++)
    for(int j = 1; j <= i; j++)
      {
        if (given[loc(i)] < given[loc(j)])
          result[loc(i, j)] = get_loc(given[loc(j)], given[loc(i)]);
        else
          result[loc(i, j)] = get_loc(given[loc(i)], given[loc(j)]);
      }
 }

void CAM::reorder(std::vector<int> *given, int *result)
{
  for(int i = 1; i <= vertex_count_; i++)
    for(int j = 1; j <= i; j++)
      {
        if ((*given)[loc(i)] < (*given)[loc(j)])
          result[loc(i, j)] = get_loc((*given)[loc(j)], (*given)[loc(i)]);
        else
          result[loc(i, j)] = get_loc((*given)[loc(i)], (*given)[loc(j)]);
      }
 }

void CAM::add_vertex(int id, int label)
{
  put_loc(id, id, label);
}

void CAM::add_edge(int id1, int id2, int label)
{
  if (id1 < id2)
    put_loc(id2, id1, label);
  else
    put_loc(id1, id2, label);
}

void CAM::print()
{
  for(int i = 1; i <= vertex_count_; i++)
    {
      for(int j = 1; j <= i; j++)
        std::cout << get_loc(i,j) << " ";
      std::cout << "\n";
    }
}

void CAM::print(int *given)
{
  for(int i = 1; i <= vertex_count_; i++)
    {
      for(int j = 1; j <= i; j++)
        std::cout << given[loc(i,j)] << " ";
      std::cout << "\n";
    }
}

void CAM::get_vertex_indices(int *indices)
{
  for(int i = 0; i < vertex_count_; i++)
    indices[i] = i + 1;  
}

void CAM::get_vertex_labels(int *labels)
{
  for(int i = 0; i < vertex_count_; i++)
    labels[i] = get_loc(i+1, i+1);  
}

void CAM::swap(int *i, int *j)
{
  int temp;
  temp = *i;
  *i = *j;
  *j = temp;
}

bool CAM::check_lower(int *given)
{
  for(int i = 1; i < (vertex_count_ * (vertex_count_ + 1))/2; i++)
    if (matrix[i] !=  given[i])
      if (matrix[i] < given[i])
        return true;
      else
        return false;
  return false;
}

bool CAM::check_maximal()
{
  int *indices, *labels, *result;

  labels = new int[vertex_count_];
  indices = new int[vertex_count_];
  result = new int[(vertex_count_ * (vertex_count_ + 1))/2];

  get_vertex_indices(indices);
  get_vertex_labels(labels);

  for(int i = 0; i < vertex_count_; i++)
    for(int j = i; j < vertex_count_; j++)
      if (labels[i] < labels[j])
        {
          swap(&labels[i],&labels[j]);
          swap(&indices[i],&indices[j]);
        }

  reorder(indices, result);

  std::cout << "Vertex sorted:\n";
  print(result);
  
  if (check_lower(result))
    {
      delete[] indices;
      delete[] labels;
      delete[] result;
      return false;
    }
  SetPermute<int> set_permute;

  int previous_label;
  std::set<int> current_set;
  for(int i = 0; i < vertex_count_; i++)
    {
      if (i == 0)
        {
          previous_label = labels[i];
          current_set.insert(indices[i]);
        }
      else
        {
          if (previous_label == labels[i])
            current_set.insert(indices[i]);
          else
            {
              set_permute.add_set(current_set);

              current_set.erase(current_set.begin(), current_set.end());
 
              previous_label = labels[i];
              current_set.insert(indices[i]);
            }
        }
    }
  set_permute.add_set(current_set);
  
  std::vector<int> curr_permutation;
  while(set_permute.get_next_permutation(&curr_permutation))
    {
      reorder(&curr_permutation, result);
      std::cout << "Permuted: ";
      for(std::vector<int>::iterator i = curr_permutation.begin(); i != curr_permutation.end(); i++)
        std::cout << *i << " ";
      std::cout << "\n";
      print(result);
      if (check_lower(result))
        {
          delete[] indices;
          delete[] labels;
          delete[] result;
          return false;
        }
    }

  delete[] indices;
  delete[] labels;
  delete[] result;
  return true;
}


int main(int argc, char *argv[])
{  
  CAM c1(3);
  c1.add_vertex(1,1);
  c1.add_vertex(2,1);
  c1.add_vertex(3,1);
  c1.add_edge(1,2,5);
  c1.add_edge(2,3,4);

  std::cout << "Original\n";
  c1.print();

  if (c1.check_maximal())
    std::cout << "Maximal\n";
  else
    std::cout << "Non maximal\n";

  return 0;
}
